package paa.simulator.grafo.simple;

import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

public class ConnectivityCounter {

	public <V extends Object> Set<Set<V>> findConnectedSets(UndirectedSimpleGraph<V> graph) {
		Set<Set<V>> components = new HashSet<Set<V>>();
		
		HashSet<V> vertexSet = new HashSet<V>(graph.vertexSet());
		HashSet<V> stack = new HashSet<V>();
		
		while (!vertexSet.isEmpty()) {
			Set<V> component = new HashSet<V>();
			components.add(component);
			
			V top = vertexSet.iterator().next();
			component.add(top);
			vertexSet.remove(top);
			
			visit(graph, vertexSet, stack, top, component);
			
			while (!stack.isEmpty()) {
				top = stack.iterator().next();
				stack.remove(top);
				component.add(top);
				vertexSet.remove(top);
				
				visit(graph, vertexSet, stack, top, component);
			}
		}
		
		return components;
	}

	private <V> void visit(UndirectedSimpleGraph<V> graph, HashSet<V> vertexSet, HashSet<V> stack, V top, Set<V> component) {
		Collection<PessoaEdge<V>> edges = graph.edgesOf(top);
		if (edges != null) {
			for (PessoaEdge<V> e : edges) {
				V relation = e.getRelation(top);
				if (!component.contains(relation)) {
					stack.add(relation);
				}
			}
		}
	}
}
